
Sparsity%2Dcognizant overlapping co%2Dclustering for behavior inference in social networks.

Residual Bayesian Co%2Dclustering for Matrix Approximation.

Keep It Simple with Time A Reexamination of Probabilistic Topic Detection Models.

Semi%2Dsupervised learning of user%2Dpreferred travel schedules.
We present a graph-based semi-supervised approach for learning user-preferred travel schedules. Assuming a setting in which a user provides a small number of labeled travel schedules, we classify schedules into desirable and non-desirable. This task is non-trivial since only a small number of labeled points is available. It is further complicated by the fact that each schedule is comprised of multiple components or aspects which are different in nature. For instance in our case arrival times are modeled by probability distributions to account for uncertainty, while other aspects such as waiting times are given by a feature vector. Each aspect can thought of as a different type of observation for the same schedule While existing label propagation approaches can exploit vast amounts of unlabeled data, they cannot handle multi-aspect data. We propose Multi-Aspect Label Propagation (MALP), a novel approach which extends label propagation to handle multiple types of observations.
Approximation Algorithms for Tensor Clustering.
We present the first (to our knowledge) approximation algorithm for tensor clustering—a powerful generalization to basic 1D clustering. Tensors are increasingly common in modern applications dealing with complex heterogeneous data and clustering them is a fundamental tool for data analysis and pattern discovery. Akin to their 1D cousins, common tensor clustering formulations are NP-hard to optimize. But, unlike the 1D case no approximation algorithms seem to be known. We address this imbalance and build on recent co-clustering work to derive a tensor clustering algorithm with approximation guarantees, allowing metrics and divergences (e.g., Bregman) as objective functions. Therewith, we answer two open questions by Anagnostopoulos et al. (2008). Our analysis yields a constant approximation factor independent of data size; a worst-case example shows this factor to be tight for Euclidean co-clustering. However, empirically the approximation factor is observed to be conservative, so our method can also be used in practice.
Discriminative Mixed%2DMembership Models.

Bayesian Overlapping Subspace Clustering.

Bayesian Cluster Ensembles.

Anomaly detection A survey.
Anomaly detection is an important problem that has been researched within diverse research areas and application domains. Many anomaly detection techniques have been specifically developed for certain application domains, while others are more generic. This survey tries to provide a structured and comprehensive overview of the research on anomaly detection. We have grouped existing techniques into different categories based on the underlying approach adopted by each technique. For each category we have identified key assumptions, which are used by the techniques to differentiate between normal and anomalous behavior. When applying a given technique to a particular domain, these assumptions can be used as guidelines to assess the effectiveness of the technique in that domain. For each category, we provide a basic anomaly detection technique, and then show how the different existing techniques in that category are variants of the basic technique. This template provides an easier and succinct understanding of the techniques belonging to each category. Further, for each category, we identify the advantages and disadvantages of the techniques in that category. We also provide a discussion on the computational complexity of the techniques since it is an important issue in real application domains. We hope that this survey will provide a better understanding of the di®erent directions in which research has been done on this topic, and how techniques developed in one area can be applied in domains for which they were not intended to begin with.
Anomaly detection using manifold embedding and its applications in transportation corridors.

Bayesian Co%2Dclustering.

Multiplicative Mixture Models for Overlapping Clustering.

I%2FO Scalable Bregman Co%2Dclustering.

Approximation Algorithms for Bregman Co%2Dclustering and Tensor Clustering

Latent Dirichlet Conditional Naive%2DBayes Models.

An Analysis of Logistic Models Exponential Family Connections and Online Performance.

Multi%2Dway Clustering on Relation Graphs.
A number of real-world domains such as social networks and e-commerce involve heterogeneous data that describes relations between multiple classes of entities. Understanding the natural structure of this type of heterogeneous relational data is essential both for exploratory analysis and for performing various predictive modeling tasks. In this paper, we propose a principled multi-way clustering framework for relational data, wherein different types of entities are simultaneously clustered based not only on their intrinsic attribute values, but also on the multiple relations between the entities. To achieve this, we introduce a relation graph model that describes all the known relations between the different entity classes, in which each relation between a given set of entity classes is represented in the form of multi-modal tensor over an appropriate domain. Our multi-way clustering formulation is driven by the objective of capturing the maximal “information ” in the original relation graph, i.e., accurately approximating the set of tensors corresponding to the various relations. This formulation is applicable to all Bregman divergences (a broad family of loss functions that includes squared Euclidean distance, KL-divergence), and also permits analysis of mixed data types using convex combinations of appropriate Bregman loss functions. Furthermore, we present a large family of structurally different multi-way clustering schemes that preserve various linear summary statistics of the original data. We accomplish the above generalizations by extending a recently proposed key theoretical result, namely the minimum Bregman information principle [1], to the relation graph setting. We also describe an efficient multi-way clustering algorithm based on alternate minimization that generalizes a number of other recently proposed clustering methods. Empirical results on datasets obtained from real-world domains (e.g., movie recommendations, newsgroup articles) demonstrate the generality and efficacy of our framework. 1
Topic Models over Text Streams A Study of Batch and Online Unsupervised Learning.

On Bayesian bounds.
We show that several important Bayesian bounds studied in machine learning, both in the batch as well as the online setting, arise by an application of a simple compression lemma. In particular, we derive (i) PAC-Bayesian bounds in the batch setting, (ii) Bayesian log-loss bounds and (iii) Bayesian bounded-loss bounds in the online setting using the compression lemma. Although every setting has different semantics for prior, posterior and loss, we show that the core bound argument is the same. The paper simplifies our understanding of several important and apparently disparate results, as well as brings to light a powerful tool for developing similar arguments for other methods. 1.
Scalable Clustering Algorithms with Balancing Constraints.
Abstract. Clustering methods for data-mining problems must be extremely scalable. In addition, several data mining applications demand that the clusters obtained be balanced, i.e., of approximately the same size or importance. In this paper, we propose a general framework for scalable, balanced clustering. The data clustering process is broken down into three steps: sampling of a small representative subset of the points, clustering of the sampled data, and populating the initial clusters with the remaining data followed by refinements. First, we show that a simple uniform sampling from the original data is sufficient to get a representative subset with high probability. While the proposed framework allows a large class of algorithms to be used for clustering the sampled set, we focus on some popular parametric algorithms for ease of exposition. We then present algorithms to populate and refine the clusters. The algorithm for populating the clusters is based on a generalization of the stable marriage problem, whereas the refinement algorithm is a constrained iterative relocation scheme. The complexity of the overall method is O(kN log N) for obtaining k balanced clusters from N data points, which compares favorably with other existing techniques for balanced clustering. In addition to providing balancing guarantees, the clustering performance obtained using the proposed framework is comparable to and often better than the corresponding unconstrained solution. Experimental results on several datasets, including
A clustering based approach to perceptual image hashing.

Model%2Dbased overlapping clustering.
While the vast majority of clustering algorithms are partitional, many real world datasets have inherently overlapping clusters. Several approaches to finding overlapping clusters have come from work on analysis of biological datasets. In this paper, we interpret an overlapping clustering model proposed by Segal et al. [23] as a generalization of Gaussian mixture models, and we extend it to an overlapping clustering model based on mixtures of any regular exponential family distribution and the corresponding Bregman divergence. We provide the necessary algorithm modifications for this extension, and present results on synthetic data as well as subsets of 20-Newsgroups and EachMovie datasets.
On the optimality of conditional expectation as a Bregman predictor.

Clustering on the Unit Hypersphere using von Mises%2DFisher Distributions.
Several large scale data mining applications, such as text categorization and gene expression analysis, involve high-dimensional data that is also inherently directional in nature. Often such data is L2 normalized so that it lies on the surface of a unit hypersphere. Popular models such as (mixtures of) multi-variate Gaussians are inadequate for characterizing such data. This paper proposes a generative mixture-model approach to clustering directional data based on the von Mises-Fisher (vMF) distribution, which arises naturally for data distributed on the unit hypersphere. In particular, we derive and analyze two variants of the Expectation Maximization (EM) framework for estimating the mean and concentration parameters of this mixture. Numerical estimation of the concentration parameters is non-trivial in high dimensions since it involves functional inversion of ratios of Bessel functions. We also formulate two clustering algorithms corresponding to the variants of EM that we derive. Our approach provides a theoretical basis for the use of cosine similarity that has been widely employed by the information retrieval community, and obtains the spherical kmeans algorithm (kmeans with cosine similarity) as a special case of both variants. Empirical results on clustering of high-dimensional text and gene-expression data based on a mixture of vMF distributions
Clustering with Bregman Divergences.

An information theoretic analysis of maximum likelihood mixture estimation for exponential families.
An important task in unsupervised learning  is maximum likelihood mixture estimation  (MLME) for exponential families. In  this paper, we prove a mathematical equivalence  between this MLME problem and  the rate distortion problem for Bregman  divergences. We also present new theoretical  results in rate distortion theory for  Bregman divergences. Further, an analysis  of the problems as a trade-o between  compression and preservation of information  is presented that yields the information  bottleneck method as an interesting  special case.
A generalized maximum entropy approach to bregman co%2Dclustering and matrix approximation.
Co-clustering is a powerful data mining technique with varied applications such as text clustering, microarray analysis and recommender systems. Recently, an informationtheoretic co-clustering approach applicable to empirical joint probability distributions was proposed. In many situations, co-clustering of more general matrices is desired. In this paper, we present a substantially generalized co-clustering framework wherein any Bregman divergence can be used in the objective function, and various conditional expectation based constraints can be considered based on the statistics that need to be preserved. Analysis of the coclustering problem leads to the minimum Bregman information principle, which generalizes the maximum entropy principle, and yields an elegant meta algorithm that is guaranteed to achieve local optimality. Our methodology yields new algorithms and also encompasses several previously known  clustering and co-clustering algorithms based on alternate minimization.
An objective evaluation criterion for clustering.
We propose and test an objective criterion for evaluation of clustering performance: How well does a clustering algorithm run on unlabeled data aid a classification algorithm? The accuracy is quantified using the PAC-MDL bound [3] in a semisupervised setting. Clustering algorithms which naturally separate the data according to (hidden) labels with a small number of clusters perform well. A simple extension of the argument leads to an objective model selection method. Experimental results on text analysis datasets demonstrate that this approach empirically results in very competitive bounds on test set performance on natural datasets.
Active Semi%2DSupervision for Pairwise Constrained Clustering.
Semi-supervised clustering uses a small amount of supervised data to aid unsupervised learning. One typical approach specifies a limited number of must-link and cannotlink  constraints between pairs of examples. This paper presents a pairwise constrained clustering framework and a new method for actively selecting informative pairwise constraints to get improved clustering performance. The clustering and active learning methods are both easily scalable to large datasets, and can handle very high dimensional data. Experimental and theoretical results confirm that this active querying of pairwise constraints significantly improves the accuracy of clustering when given a relatively small amount of supervision.
Clustering with Bregman Divergences.

Generative model%2Dbased clustering of directional data.
 
Semi%2Dsupervised Clustering by Seeding.
Semi-supervised clustering uses a small  amount of labeled data to aid and bias the  clustering of unlabeled data. This paper explores  the use of labeled data to generate  initial seed clusters, as well as the use of  constraints generated from labeled data to  guide the clustering process. It introduces  two semi-supervised variants of KMeans clustering  that can be viewed as instances of the  EM algorithm, where labeled data provides  prior information about the conditional distributions  of hidden category labels. Experimental  results demonstrate the advantages of  these methods over standard random seeding  and COP-KMeans, a previously developed  semi-supervised clustering algorithm.
On Scaling Up Balanced Clustering Algorithms.
&amp;quot;rand01 &amp;quot;-- 2003/4/14-- 10:12-- page 1-- #1 i i i i
